package leetcode;

/*
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7
 
限制：
0 <= 节点个数 <= 5000
*/

import java.util.HashSet;
import java.util.Set;

public class Offer_007 {
    public static void main(String[] args) {
        System.out.println(new Solution().buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7}));
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /***
     * 思路：
     * 拆分的方法，比如例子：
     *  [3,9,20,15,7]
     *  [9,3,15,20,7]
     *
     *  root节点必须是前序首节点，3，然后中序中，3的首节点分成左右，左边是左节点组，右边是右节点的组。
     *  所以左节点：[9]，右节点[15,20,7]
     *  前序，[3]之后,[9]是左边，[20,15,7]是右
     *  所以：
     *    1，中序左边右边，节点组，每组的长度和前序是一致的
     *    2，前序，每组是首节点就是组的根节点
     */
    static class Solution {
        // 生成二叉树
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (null == preorder || null == inorder || preorder.length == 0 || inorder.length == 0) return null;
            TreeNode treeNode = new TreeNode(preorder[0]);
            // 追加节点
            addTreeNode(treeNode, preorder, inorder, 0, preorder.length - 1);
            // 返回值
            return treeNode;
        }
        // 追加节点
        public void addTreeNode(TreeNode treeNode, int[] preorder, int[] inorder, int start, int end) {
            System.out.println(String.format("val:%s --start：%s end：%s ", String.valueOf(treeNode.val), String.valueOf(start), String.valueOf(end)));
            // 根节点
            int rootInIndex = findIndex(preorder, treeNode.val); // 前序索引
            int rootPreIndex = findIndex(inorder, treeNode.val); // 中序索引
            // 左右节点长度
            int lenLeft = rootPreIndex - start;
            int lenRight = end - rootPreIndex;
            // 左节点
            if(lenLeft > 0){
                TreeNode leftNode = new TreeNode(preorder[rootInIndex + 1]);
                treeNode.left = leftNode;
                addTreeNode(leftNode, preorder, inorder, start, start + lenLeft - 1);
            }
            // 右节点
            if(lenRight > 0){
                TreeNode rightNode = new TreeNode(preorder[rootInIndex + lenLeft + 1]);
                treeNode.right = rightNode;
                addTreeNode(rightNode, preorder, inorder, end - lenRight + 1, end);
            }
        }
        // 找索引
        private int findIndex(int[] arr, int val) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == val) return i;
            }
            return -1;
        }

    }
}

